/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/interleaving-positive-and-negative-numbers
   @Language: C++
   @Datetime: 16-02-09 05:53
   */

class Solution {
public:
	/**
	 * @param A: An integer array.
	 * @return: void
	 * Steps: move all negative to left and positive to right,
	 *        statistics negative count (can upon above),
	 *        from left to right interleave element by step 2
	 */
	void rerange(vector<int> &A) {
		// write your code here
		int l=0, r=A.size()-1, neg=0;
		for (; l<r; swap(A[l],A[r])){
			for(; l<r && A[l]<0; ++l);
			for(; l<r && A[r]>0; --r);
			if (l >= r) break;
		}
		neg=l, l=0, r=A.size()-1;
		if(neg*2 < A.size()) --r;
		else if (neg*2 > A.size()) ++l;
		// else : no answer
		for(; l<r; l+=2,r-=2)
			swap(A[l],A[r]);
	}
};
